/* 
 * File:   main.cpp
 * Author: jinjill
 * Palindrome Partition II
 * Given a string s, partition s such that every substring of the partition is a palindrome.
   Return the minimum cuts needed for a palindrome partitioning of s.
   For example, given s = "aab",
   Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
 * 
 * Created on July 12, 2013, 7:38 AM
 */

#include <cstdlib>
#include <stdlib.h>
#include <iostream>;
#include <vector>;

using namespace std;

struct TriSubstring
{
    string left;
    string value;
    string right;
    int startpos;
    int endpos;
    int length;
};


int string_length(char *string)
{
   int length = 0;

   while(*string)
   {
      length++;
      string++;
   }

   return length;
}


bool is_palindrome(char *string)
{
   int length = string_length(string);
   int begin=0;
   int end=length-1;
   for(;begin<end;begin++,end--)
   {
	   if(*(string+begin)!=*(string+end))
	   {
		 return false;
	   }
   }
   return true;
}



vector<TriSubstring> GenerateSubstringByLength(char* input, int len)
{

    vector<TriSubstring> vsubstring;
 TriSubstring trisub;
	int length = string_length(input);

	for(int i=0;i<=length-len;i++)
	{
		vector<char> substrings;
		for(int j=0;j<len;j++)
		{
                    if((input+i+j))
                    {
                       substrings.push_back(*(input+i+j));

                    }
                    
		}
                substrings.push_back('\0');

                char *p = reinterpret_cast<char*> (&substrings[0]);
            
                int palinlength = string_length(p);
                if(is_palindrome(p) && (palinlength>1))
                {
                    
                    char left[i+1];
                    char value[len+1];
                    char right[length-i-len+1];
                    
                    strncpy(left, input, i);
                    left[i]='\0';
                    (trisub.left) = left;
                
                    strncpy(value, input+i, len);
                    value[len]='\0';
                    trisub.value = value;
                    trisub.startpos = i;
                    trisub.endpos=i+len-1;
                    trisub.length = len;
                    
                    strncpy(right, input+i+len, length-(i+len));
                    right[length-(i+len)]='\0';
                    trisub.right = right;

                    vsubstring.push_back(trisub);
                }
	}
         return vsubstring;

}

bool MarkFlag(int flags[],int start,int end)
{
    for(int i=start;i<=end;i++)
    {
        if(flags[i]==0)
        {
            flags[i]=1;
        }
        else
        {
            for(int j=start;j<i;j++)
            {
                flags[j]=0;
            }
            return false;
        }
    }
    return true;
}

/*
 * 
 */
int main(int argc, char** argv) {

    string str="apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp";

     int cuts = std::numeric_limits<int>::max();
	char *cstr = new char[str.length() + 1];
	strcpy(cstr, str.c_str());
        
	int length = str.length();

        vector<TriSubstring> totalsubs;

	for(int i=length;i>0;i--)
	{
             vector<TriSubstring> trisubs = GenerateSubstringByLength(cstr,i);
              for (vector<TriSubstring>::iterator it = trisubs.begin() ; it != trisubs.end(); ++it)
              {
                  totalsubs.push_back(*it);
              }
        }
        
            
             if(totalsubs.size()==0)
             {
                 cout<<"Cuts:"<<length-1;
             }
             else
             {
                 int maxLength =0;
                 int totalSubLength=0;
                 int segmentsCount =0;
                
             for (vector<TriSubstring>::iterator it = totalsubs.begin() ; it != totalsubs.end(); ++it)
             {
                 int flags[length];
                 segmentsCount =0;
                 totalSubLength=0;
                 for(int i=0;i<length;i++)
                 {
                     flags[i]=0;
                 }
                 MarkFlag(flags,it->startpos,it->endpos);
                 segmentsCount=1;
                 totalSubLength=it->length;
               
                 for (vector<TriSubstring>::iterator it2 = totalsubs.begin(); it2 != totalsubs.end(); ++it2)
                 {
                     if(it==it2)
                         continue;
                     
                     if(MarkFlag(flags,it2->startpos,it2->endpos))
                     {
                        
                      
                         segmentsCount++;
                         totalSubLength = totalSubLength+it2->length;                       
                     }
                 }
                 if(maxLength<totalSubLength)
                  {
                      maxLength = totalSubLength;
                  
                  }
                 int singlePolindrome = length-maxLength;
                 if((singlePolindrome+segmentsCount)<cuts)
                 {
                     cuts=singlePolindrome+segmentsCount;
                 }
                 if(segmentsCount==1&&singlePolindrome==0)
                     cuts=0;
                  
            
             }  
                 
               //int singlePolindrome = length-maxLength;
               //cout<<"single:"<<singlePolindrome;
        cout<<"cuts:"<<cuts;
	}
      
    return cuts;
}
